package com.example.system.class07;

import java.util.Arrays;

/**
 * @Date 2022/7/24
 * @Author Jonathan
 */
public class Code02_HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 1, 2, 4, 9, 8, 6};
        // heapSort(arr);
        heapSort1(arr);
        System.out.println(Arrays.toString(arr));
    }


    public static void heapSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            // 从最后一个非终端页节点开始调整堆
            int lastNonLeaf = (arr.length - i - 2) / 2;
            // 每调整一轮就是一个大顶堆 然后将这个最大值放到最后面，然后最后面就不参与下一轮堆调整
            // 一共进行n-1轮即可
            for (int j = lastNonLeaf; j >= 0; j--) {
                // 选择左孩子 右孩子 和父亲节点里面的最大值
                int maxIndex = 2 * j + 1;
                // 右孩子存在的情况下才比较
                if (maxIndex + 1 <= (arr.length - 1 - i) && arr[maxIndex + 1] > arr[maxIndex]) {
                    maxIndex = maxIndex + 1;
                }
                if (arr[j] < arr[maxIndex]) {
                    swap(arr, j, maxIndex);
                }
                // 遍历完一遍之后就是一个大顶堆
            }
            swap(arr, 0, arr.length - i - 1);
        }
    }


    public static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void heapSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        // O(N*logN)
//		for (int i = 0; i < arr.length; i++) { // O(N)
//			heapInsert(arr, i); // O(logN)
//		}
        // O(N)
        for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        // O(N*logN)
        while (heapSize > 0) { // O(N)
            heapify(arr, 0, heapSize); // O(logN)
            swap(arr, 0, --heapSize); // O(1)
        }

    }


    // arr[index]刚来的数，往上
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int[] arr, int index, int heapSize) {
        // 调整堆
        int left = index * 2 + 1; // 左孩子的下标
        while (left < heapSize) {
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }
}
